package medium;//字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
//
//
// 序列中第一个单词是 beginWord 。
// 序列中最后一个单词是 endWord 。
// 每次转换只能改变一个字母。
// 转换过程中的中间单词必须是字典 wordList 中的单词。
//
//
// 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中
//的 单词数目 。如果不存在这样的转换序列，返回 0。
//
//
// 示例 1：
//
//
//输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","lo
//g","cog"]
//输出：5
//解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
//
//
// 示例 2：
//
//
//输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","lo
//g"]
//输出：0
//解释：endWord "cog" 不在字典中，所以无法进行转换。
//
//
//
// 提示：
//
//
// 1 <= beginWord.length <= 10
// endWord.length == beginWord.length
// 1 <= wordList.length <= 5000
// wordList[i].length == beginWord.length
// beginWord、endWord 和 wordList[i] 由小写英文字母组成
// beginWord != endWord
// wordList 中的所有字符串 互不相同
//
// Related Topics 广度优先搜索 哈希表 字符串
// 👍 838 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
public class L127 {

    public static void main(String[] args) {
        System.out.println(ladderLength("hit","cog",Arrays.asList("hot","dot","dog","lot","log","cog")));
    }

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //广度优先搜索，去除已经访问过的。时间O(n*c^2) 空间O(n*c^2)
        Deque<String> wordDeque = new ArrayDeque<>();
        wordDeque.offerLast(beginWord);
        int count = 1;
        while (!wordDeque.isEmpty()) {
            int size = wordDeque.size();
            count++;
            for (int i = 0; i < size; i++) {
                String s = wordDeque.pollLast();
                for (int j = 0; j < s.length(); j++) {
                    Iterator<String> iterator = wordList.iterator();
                    while (iterator.hasNext()){
                        String s1 = iterator.next();
                        boolean same = true;
                        for (int i1 = 0; i1 < s1.length(); i1++) {
                            if (i1 == j) continue;
                            if (s1.charAt(i1) != s.charAt(i1)) {
                                same = false;
                                break;
                            }
                        }
                        if (!same) {
                            continue;
                        }
                        if (s1.equals(endWord)) {
                            return count;
                        }
                        wordDeque.offerFirst(s1);
                        iterator.remove();
                    }
                    //改变为
                }
            }
        }
        return 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
